package com.leetcode;

/**
 * 删除链表倒数第N个节点
 *
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 *
 * @author winson
 * @create 2022-03-29 11:47
 */
public class RemoveNthFromEndSolution {

    /**
     * 通过快慢指针，定位倒数第N个节点
     * 快指针先走N - 1步，然后快慢指针相同速度一起走，直到快指针达到最后一个节点，此时慢指针就是倒数N个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode listNode = new ListNode(0, head);
        ListNode fast = listNode;
        n--;
        while (n > 0 && fast != null) {
            fast = fast.next;
            n--;
        }
        ListNode slow = listNode;
        ListNode slowPre = null;
        while (fast.next != null) {
            fast = fast.next;
            slowPre = slow;
            slow = slow.next;
        }
        slowPre.next = slow.next;
        return listNode.next;
    }
}
